#include <iostream>
using namespace std;
int t, n, m, a, b;
int main(){
	cin >> t;
	while(t--){
		cin >> n >> m;
		int cnt = 0, flag = 0;
		while(n--){
			cin >> a >> b;
			if (a % 2 == 0 && b % 2 != flag){
				cnt++;
				flag = flag == 1 ? 0 : 1;
			}
			else if (a % 2 == 1 && b % 2 == flag){
				cnt++;
				flag = flag == 1 ? 0 : 1;
			}
		}
		cout << m - cnt << endl;
	}

    return 0;
}


